package com.my.study.structures.sort;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 冒泡排序
 *
 * 基本思想：通过对 待排序系列从前到后（从下标较小的元素开始），
 *          依次比较相邻元素的值，若发现逆序则交换，使得较大的值逐渐从前移向后部，
 *          就像水底下的气泡一样逐渐向上冒。
 *
 *  规则：
 *       (1) 一共进行数组大小-1次大的循环
 *       (2) 每一趟排序的次数在逐渐的减少
 *       (3) 在某趟排序中没发生一次交换，就可以结束排序
 *
 *
 *
 *
 * @date 2021/7/8 22:38
 **/
public class BubbleSort {


    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        sortAsc(arr);
        System.out.println("==================");
        sortDesc(arr);
    }

    /**
     * 升序
     *
     * @param arr
     */
    private static void sortAsc(int[] arr) {
        int len = arr.length - 1;
        //临时变量，用于swap
        int temp = 0;
        for (int i = 0; i < len; i++) {
            int innerLen = len - i;
            for (int j = 0; j < innerLen; j++) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第" + (i+1) + "次排序");
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 降序
     *
     * @param arr
     */
    private static void sortDesc(int[] arr) {
        int len = arr.length - 1;
        int temp = 0;
        for (int i = 0; i < len; i++) {
            for (int j = len; j > i; j--) {
                if (arr[j] > arr[j-1]) {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
            System.out.println("第" + (i+1) + "次排序");
            System.out.println(Arrays.toString(arr));
        }
    }


    private static void sortFlag(int[] arr) {
        int len = arr.length - 1;
        //临时变量，用于swap
        int temp = 0;
        // 标识变量，表示是否发生过交换
        boolean flag = false;
        for (int i = 0; i < len; i++) {
            int innerLen = len - i;
            for (int j = 0; j < innerLen; j++) {
                if (arr[j] > arr[j+1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第" + (i+1) + "次排序");
            System.out.println(Arrays.toString(arr));
            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }
    }


}
